package interviewQuestions;

// 剑指offer5题
/**
 * 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
 *
 * 示例：
 * 输入：s = "We are happy."
 * 输出："We%20are%20happy."
 * */
public class ReplaceSpace {
    /**
     * 第一种方法：将字符串拷贝到新数组
     * 思路：
     * 遍历字符串，并逐个拷贝到新数组中，当遇到空格的时候，在数组中添加%20
     */

    public static String solve1(String s){
        // 定义一个数组，长度为字符串长度的三倍（考虑到全部是空格）
        char[] chars = new char[s.length()*3];
        int i = 0;
        int k = 0;
        for (i = 0; i < s.length(); i++) {
            if(s.charAt(i) == ' '){ // 如果当前字符为空格，那么在数组中添加%20
                chars[k++] = '%';
                chars[k++] = '2';
                chars[k++] = '0';

            }else{
                chars[k++] = s.charAt(i);
            }
        }
        return String.valueOf(chars).trim();
    }


    /**
     * 第二种方法：原地替换
     * 思路：首先计算出空格出现的次数，然后将当前的字符串长度扩容到 原长度+次数*2
     * 用两个指针一个指向扩容后字符串的末尾，一个指向原来字符串的最后一个字符
     * 然后，如果是非空格字符的话，直接拷贝到末尾指针处，然后往前遍历
     *
     * 这个剑指offer讲的很清楚，很多时候，我们在进行字符串操作的时候，也要考虑到倒序遍历
     * 由于Java中的String是不可变的，所以这里就不写代码了
     * */

    // main
    public static void main(String[] args) {
        String s = solve1("we are kid");
        System.out.println(s);
    }
}
